home *** CD-ROM | disk | FTP | other *** search
/ Shareware Grab Bag / Shareware Grab Bag.iso / 007 / wart.arc / WART.C next >
Encoding:
C/C++ Source or Header  |  1985-06-27  |  12.6 KB  |  624 lines
  1.  
  2. /* W A R T
  3.  *
  4.  * pre-process a lex-like file into a C program.
  5.  *
  6.  * Jeff Damens, Columbia University Center for Computing Activites, 11/84.
  7.  * (Reorganized by Frank da Cruz into a single source module for ease
  8.  * of distribution).
  9.  * Copyright (C) 1984, Trustees of Columbia University.
  10.  * May be copied and used except for explicitly commercial purposes.
  11.  *
  12.  * input format is:
  13.  *  lines to be copied | %state <state names...>
  14.  *  %%
  15.  * <state> | <state,state,...> CHAR  { actions }
  16.  * ...
  17.  *  %%
  18.  */
  19.  
  20. #include <stdio.h>
  21. #include <ctype.h>
  22.  
  23. #define DEBUG 0
  24. /* token types */
  25.  
  26. #define SEP 1
  27. #define LBRACK 2
  28. #define RBRACK 3
  29. #define WORD 4
  30. #define COMMA 5
  31.  
  32. /* storage sizes */
  33.  
  34. #define MAXSTATES 50            /* max number of states */
  35. #define MAXWORD 50            /* max # of chars/word */
  36. #define SBYTES ((MAXSTATES+7)/8)    /* # of bytes for state bitmask */
  37.  
  38. /* name of wart function in generated program */
  39.  
  40. #ifndef FNAME
  41. #define FNAME "wart"
  42. #endif
  43.  
  44. /* data structure for state information */
  45.  
  46. typedef char CHAR;
  47.  
  48. struct trans { CHAR states[SBYTES];    /* included states */
  49.            int anyst;        /* true if this good from any state */
  50.            CHAR inchr;        /* input character */
  51.            int actno;        /* associated action */
  52.            struct trans *nxt; };    /* next transition */
  53.  
  54. typedef struct trans *Trans;
  55.  
  56. /* Variables and tables */
  57.  
  58. int lines,nstates,nacts;
  59.  
  60. char tokval[MAXWORD];
  61.  
  62. int tbl[MAXSTATES*128];
  63.  
  64.  
  65.  
  66. char *txt1 = "\n\
  67. #define BEGIN state =\n\
  68. \n\
  69. int state = 0;\n\
  70. \n";
  71.  
  72. char *fname = FNAME;        /* function name goes here */
  73.  
  74. /* rest of program... */
  75.  
  76. char *txt2 = "()\n\
  77. {\n\
  78.   int c,actno;\n\
  79.   extern int tbl[];\n\
  80.   while (1) {\n\
  81.     c = input();\n\
  82.     if ((actno = tbl[c + state*128]) != -1)\n\
  83.       switch(actno) {\n";
  84.  
  85. /* this program's output goes here, followed by final text... */
  86.  
  87. char *txt3 = "\n    }\n  }\n\}\n\n";
  88.  
  89. /*
  90.  * turn on the bit associated with the given state
  91.  *
  92.  */
  93. setstate(state,t)
  94. int state;
  95. Trans t;
  96. {
  97.   int idx,msk;
  98.   idx = state/8;            /* byte associated with state */
  99.   msk = 0x80 >> (state % 8);        /* bit mask for state */
  100.   t->states[idx] |= msk;
  101. }
  102.  
  103. /*
  104.  * see if the state is involved in the transition
  105.  *
  106.  */
  107.  
  108. teststate(state,t)
  109. int state;
  110. Trans t;
  111. {
  112.   int idx,msk;
  113.   idx = state/8;
  114.   msk = 0x80 >> (state % 8);
  115.   return(t->states[idx] & msk);
  116. }
  117.  
  118.  
  119. /*
  120.  * read input from here...
  121.  *
  122.  */
  123.  
  124. Trans
  125. rdinput(infp,outfp)
  126. FILE *infp,*outfp;
  127. {
  128.   Trans x,rdrules();
  129.   lines = 1;                /* line counter */
  130.   nstates = 0;                /* no states */
  131.   nacts = 0;                /* no actions yet */
  132.   fprintf(outfp,"\n\
  133. /* WARNING -- This C source program generated by Wart preprocessor. */\n");
  134.   fprintf(outfp,"\
  135. /* Do not edit this file; edit the Wart-format source file instead, */\n");
  136.   fprintf(outfp,"\
  137. /* and then run it through Wart to produce a new C source file.     */\n\n");
  138.   initial(infp,outfp);            /* read state names, initial defs */
  139.   prolog(outfp);            /* write out our initial code */
  140.   x = rdrules(infp,outfp);        /* read rules */
  141.   epilogue(outfp);            /* write out epilogue code */
  142.   return(x);
  143. }
  144.  
  145. /*
  146.  * initial - read initial definitions and state names.    Returns
  147.  * on EOF or %%.
  148.  *
  149.  */
  150.  
  151. initial(infp,outfp)
  152. FILE *infp,*outfp;
  153. {
  154.   int c;
  155.   char wordbuf[MAXWORD];
  156.   while ((c = getc(infp)) != EOF) {
  157.     if(DEBUG) printf("INITIAL: c = %c\n",c);
  158.     if (c == '%') {
  159.             rdword(infp,wordbuf);
  160.             if (strcmp(wordbuf,"states") == 0)
  161.                 rdstates(infp,outfp);
  162.             else if (strcmp(wordbuf,"%") == 0) return;
  163.             else fprintf(outfp,"%%%s",wordbuf);
  164.               }
  165.     else putc(c,outfp);
  166.     if (c == '\n') lines++;
  167.      }
  168. }
  169.  
  170. /*
  171.  * boolean function to tell if the given character can be part of
  172.  * a word.
  173.  *
  174.  */
  175. isin(s,c) char *s; int c; {
  176.    for (; *s != '\0'; s++)
  177.       if (*s == c) return(1);
  178.    return(0);
  179. }
  180. isword(c)
  181. int c;
  182. {
  183.   static char special[] = ".%_-$@";     /* these are allowable */
  184.   return(isalnum(c) || isin(special,c));
  185. }
  186.  
  187. /*
  188.  * read the next word into the given buffer.
  189.  *
  190.  */
  191. rdword(fp,buf)
  192. FILE *fp;
  193. char *buf;
  194. {
  195.   int len = 0,c;
  196.   while (isword(c = getc(fp)) && ++len < MAXWORD) *buf++ = c;
  197.   *buf++ = '\0';                        /* tie off word */
  198.   if(DEBUG) printf("RDWORD:buf = %s\n",buf);
  199.   ungetc(c,fp);             /* put break char back */
  200. }
  201.  
  202. /*
  203.  * read state names, up to a newline.
  204.  *
  205.  */
  206.  
  207. rdstates(fp,ofp)
  208. FILE *fp,*ofp;
  209. {
  210.   int c;
  211.   char wordbuf[MAXWORD];
  212.   while ((c = getc(fp)) != EOF && c != '\n')
  213.   {
  214.     if (isspace(c)) continue;    /* skip whitespace */
  215.     ungetc(c,fp);            /* put char back */
  216.     rdword(fp,wordbuf);        /* read the whole word */
  217.     if(DEBUG) printf("RDSTATES: wordbuf = %s\n",wordbuf);
  218.     enter(wordbuf,++nstates);    /* put into symbol tbl */
  219.     fprintf(ofp,"#define %s %d\n",wordbuf,nstates);
  220.   }
  221.   lines++;
  222. }
  223.  
  224. /*
  225.  * allocate a new, empty transition node
  226.  *
  227.  */
  228.  
  229. Trans
  230. newtrans()
  231. {
  232.   Trans new;
  233.   int i;
  234.   new = (Trans) malloc(sizeof (struct trans));
  235.   for (i=0; i<SBYTES; i++) new->states[i] = 0;
  236.   new->anyst = 0;
  237.   new->nxt = NULL;
  238.   return(new);
  239. }
  240.  
  241. /*
  242.  * read all the rules.
  243.  *
  244.  */
  245.  
  246. Trans
  247. rdrules(fp,out)
  248. FILE *fp,*out;
  249. {
  250.   Trans head,cur,prev;
  251.   int curtok,i;
  252.   head = cur = NULL;
  253.   while ((curtok = gettoken(fp)) != SEP)
  254.  
  255.     switch(curtok) {
  256.         case LBRACK: if (cur == NULL) cur = newtrans();
  257.                  else fatal("duplicate state list");
  258.                  statelist(fp,cur);/* set states */
  259.                  continue;    /* prepare to read char */
  260.  
  261.         case WORD:   if (strlen(tokval) != 1)
  262.                     fatal("multiple chars in state");
  263.                  if (cur == NULL) {
  264.                 cur = newtrans();
  265.                 cur->anyst = 1;
  266.                 }
  267.                  cur->actno = ++nacts;
  268.                  cur->inchr = tokval[0];
  269.                  if (head == NULL) head = cur;
  270.                  else prev->nxt = cur;
  271.                  prev = cur;
  272.                  cur = NULL;
  273.                  copyact(fp,out,nacts);
  274.                  break;
  275.          default: fatal("bad input format");
  276.          }
  277.  
  278.    return(head);
  279. }
  280.  
  281. /*
  282.  * read a list of (comma-separated) states, set them in the
  283.  * given transition.
  284.  *
  285.  */
  286. statelist(fp,t)
  287. FILE *fp;
  288. Trans t;
  289. {
  290.   int curtok,sval;
  291.   curtok = COMMA;
  292.   while (curtok != RBRACK) {
  293.     if (curtok != COMMA) fatal("missing comma");
  294.     if ((curtok = gettoken(fp)) != WORD) fatal("missing state name");
  295.     if ((sval = lkup(tokval)) == -1) {
  296.         fprintf(stderr,"state %s undefined\n",tokval);
  297.         fatal("undefined state");
  298.        }
  299.     setstate(sval,t);
  300.     curtok = gettoken(fp);
  301.    }
  302. }
  303.  
  304. /*
  305.  * copy an action from the input to the output file
  306.  *
  307.  */
  308. copyact(inp,outp,actno)
  309. FILE *inp,*outp;
  310. int actno;
  311. {
  312.   int c,bcnt;
  313.   fprintf(outp,"case %d:\n",actno);
  314.   while ((c = getc(inp)) != '\n' && isspace(c));        /* skip whitespace */
  315.   if (c == '{') {
  316.      bcnt = 1;
  317.      putc(c,outp);
  318.      while (bcnt > 0 && (c = getc(inp)) != EOF) {
  319.     if (c == '{') bcnt++;
  320.     else if (c == '}') bcnt--;
  321.     else if (c == '\n') lines++;
  322.     putc(c,outp);
  323.       }
  324.      if (bcnt > 0) fatal("action doesn't end");
  325.     }
  326.    else {
  327.       while (c != '\n' && c != EOF) {
  328.         putc(c,outp);
  329.         c = getc(inp);
  330.         }
  331.       lines++;
  332.     }
  333.    fprintf(outp,"\nbreak;\n");
  334. }
  335.  
  336. /*
  337.  * find the action associated with a given character and state.
  338.  * returns -1 if one can't be found.
  339.  *
  340.  */
  341. faction(hd,state,chr)
  342. Trans hd;
  343. int state,chr;
  344. {
  345.   while (hd != NULL) {
  346.     if (hd->anyst || teststate(state,hd))
  347.       if (hd->inchr == '.' || hd->inchr == chr) return(hd->actno);
  348.     hd = hd->nxt;
  349.     }
  350.   return(-1);
  351. }
  352.  
  353.  
  354. /*
  355.  * empty the table...
  356.  *
  357.  */
  358. emptytbl()
  359. {
  360.   int i;
  361.   for (i=0; i<nstates*128; i++) tbl[i] = -1;
  362. }
  363.  
  364. /*
  365.  * add the specified action to the output for the given state and chr.
  366.  *
  367.  */
  368.  
  369. addaction(act,state,chr)
  370. int act,state,chr;
  371. {
  372.  tbl[state*128 + chr] = act;
  373. }
  374.  
  375. writetbl(fp)
  376. FILE *fp;
  377. {
  378.   warray(fp,"tbl",tbl,128*(nstates+1));
  379. }
  380.  
  381. /*
  382.  * write an array to the output file, given its name and size.
  383.  *
  384.  */
  385. warray(fp,nam,cont,siz)
  386. FILE *fp;
  387. char *nam;
  388. int cont[],siz;
  389. {
  390.   int i;
  391.   fprintf(fp,"int %s[] = {\n",nam);
  392.   for (i = 0; i < siz; i++) {
  393.     fprintf(fp,"%d, ",cont[i]);
  394.     if ((i % 20) == 0) putc('\n',fp);
  395.     }
  396.   fprintf(fp,"};\n");
  397. }
  398.  
  399. main(argc,argv)
  400. int argc;
  401. char *argv[];
  402. {
  403.   Trans head;
  404.   int state,c;
  405.   FILE *infile,*outfile;
  406.  
  407.   if (argc > 1) {
  408.     if ((infile = fopen(argv[1],"r")) == NULL) {
  409.     fprintf(stderr,"Can't open %s\n",argv[1]);
  410.     fatal("unreadable input file"); } }
  411.   else infile = stdin;
  412.  
  413.   if (argc > 2) {
  414.     if ((outfile = fopen(argv[2],"w")) == NULL) {
  415.     fprintf(stderr,"Can't write to %s\n",argv[2]);
  416.     fatal("bad output file"); } }
  417.   else outfile = stdout;
  418.  
  419.   clrhash();                /* empty hash table */
  420.   head = rdinput(infile,outfile);    /* read input file */
  421.   emptytbl();                /* empty our tables */
  422.   for (state = 0; state <= nstates; state++)
  423.     for (c = 1; c < 128; c++)
  424.      addaction(faction(head,state,c),state,c);    /* find actions, add to tbl */
  425.   writetbl(outfile);
  426.   copyrest(infile,outfile);
  427.   printf("%d states, %d actions\n",nstates,nacts);
  428. #ifdef undef
  429.   for (state = 1; state <= nstates; state ++)
  430.     for (c = 1; c < 128; c++)
  431.        if (tbl[state*128 + c] != -1) printf("state %d, chr %d, act %d\n",
  432.     state,c,tbl[state*128 + c]);
  433. #endif
  434.   exit(0);
  435. }
  436.  
  437. /*
  438.  * fatal error handler
  439.  *
  440.  */
  441.  
  442. fatal(msg)
  443. char *msg;
  444. {
  445.   fprintf(stderr,"error in line %d: %s\n",lines,msg);
  446.   exit(1);
  447. }
  448.  
  449. prolog(outfp)
  450. FILE *outfp;
  451. {
  452.   int c;
  453.   while ((c = *txt1++) != '\0')  putc(c,outfp);
  454.   while ((c = *fname++) != '\0') putc(c,outfp);
  455.   while ((c = *txt2++) != '\0')  putc(c,outfp);
  456. }
  457.  
  458. epilogue(outfp)
  459. FILE *outfp;
  460. {
  461.   int c;
  462.   while ((c = *txt3++) != '\0') putc(c,outfp);
  463. }
  464.  
  465. copyrest(in,out)
  466. FILE *in,*out;
  467. {
  468.   int c;
  469.   while ((c = getc(in)) != EOF) putc(c,out);
  470. }
  471.  
  472. /*
  473.  * gettoken - returns token type of next token, sets tokval
  474.  * to the string value of the token if appropriate.
  475.  *
  476.  */
  477.  
  478. gettoken(fp)
  479. FILE *fp;
  480. {
  481.   int c;
  482.   while (1) {                /* loop if reading comments... */
  483.     do {
  484.       c = getc(fp);
  485.       if (c == '\n') lines++;
  486.        } while (isspace(c));        /* skip whitespace */
  487.     switch(c) {
  488.       case EOF: return(SEP);
  489.       case '%': if ((c = getc(fp)) == '%') return(SEP);
  490.             tokval[0] = '%';
  491.             tokval[1] = c;
  492.             rdword(fp,tokval+2);
  493.             return(WORD);
  494.       case '<': return(LBRACK);
  495.       case '>': return(RBRACK);
  496.       case ',': return(COMMA);
  497.       case '/': if ((c = getc(fp)) == '*') {
  498.               rdcmnt(fp);    /* skip over the comment */
  499.               continue; }    /* and keep looping */
  500.             else {
  501.             ungetc(c);    /* put this back into input */
  502.             c = '/'; }      /* put character back, fall thru */
  503.  
  504.       default: if (isword(c)) {
  505.               ungetc(c,fp);
  506.               rdword(fp,tokval);
  507.               return(WORD);
  508.             }
  509.            else fatal("Invalid character in input");
  510.          }
  511.   }
  512. }
  513.  
  514. /*
  515.  * skip over a comment
  516.  *
  517.  */
  518.  
  519. rdcmnt(fp)
  520. FILE *fp;
  521. {
  522.   int c,star,prcnt;
  523.   prcnt = star = 0;            /* no star seen yet */
  524.   while (!((c = getc(fp)) == '/' && star)) {
  525.     if (c == EOF || (prcnt && c == '%')) fatal("Unterminated comment");
  526.     prcnt = (c == '%');
  527.     star = (c == '*');
  528.     if (c == '\n') lines++; }
  529. }
  530.  
  531.  
  532. /*
  533.  * symbol table management for wart
  534.  *
  535.  * entry points:
  536.  *   clrhash - empty hash table.
  537.  *   enter - enter a name into the symbol table
  538.  *   lkup - find a name's value in the symbol table.
  539.  *
  540.  */
  541.  
  542. #define HASHSIZE 101            /* # of entries in hash table */
  543.  
  544. struct sym { char *name;        /* symbol name */
  545.          int val;            /* value */
  546.          struct sym *hnxt; }    /* next on collision chain */
  547.     *htab[HASHSIZE];            /* the hash table */
  548.  
  549.  
  550. /*
  551.  * empty the hash table before using it...
  552.  *
  553.  */
  554. clrhash()
  555. {
  556.   int i;
  557.   for (i=0; i<HASHSIZE; i++) htab[i] = NULL;
  558. }
  559.  
  560. /*
  561.  * compute the value of the hash for a symbol
  562.  *
  563.  */
  564. hash(name)
  565. char *name;
  566. {
  567.   int sum;
  568.   for (sum = 0; *name != '\0'; name++) sum += (sum + *name);
  569.   sum %= HASHSIZE;            /* take sum mod hashsize */
  570.   if (sum < 0) sum += HASHSIZE;     /* disallow negative hash value */
  571.   return(sum);
  572. }
  573.  
  574. /*
  575.  * make a private copy of a string...
  576.  *
  577.  */
  578. char *
  579. copy(s)
  580. char *s;
  581. {
  582.   char *new;
  583.   new = (char *) malloc(strlen(s) + 1);
  584.   strcpy(new,s);
  585.   return(new);
  586. }
  587.  
  588. /*
  589.  * enter state name into the hash table
  590.  *
  591.  */
  592. enter(name,svalue)
  593. char *name;
  594. int svalue;
  595. {
  596.   int h;
  597.   struct sym *cur;
  598.   if (lkup(name) != -1) {
  599.     fprintf(stderr,"state %s appears twice...\n",name);
  600.     exit(1); }
  601.   h = hash(name);
  602.   cur = (struct sym *)malloc(sizeof (struct sym));
  603.   cur->name = copy(name);
  604.   cur->val = svalue;
  605.   cur->hnxt = htab[h];
  606.   htab[h] = cur;
  607. }
  608.  
  609. /*
  610.  * find name in the symbol table, return its value.  Returns -1
  611.  * if not found.
  612.  *
  613.  */
  614. lkup(name)
  615. char *name;
  616. {
  617.   struct sym *cur;
  618.   for (cur = htab[hash(name)]; cur != NULL; cur = cur->hnxt)
  619.     if (strcmp(cur->name,name) == 0) return(cur->val);
  620.   return(-1);
  621. }
  622.  
  623.  
  624.